% Idan Elad, 039452396, sidane@t2
% Erez Druk, 300586088, druk@cs

%Question 1
member(X, [X |_]).
member(X, [_| Tail]) :-
	member(X, Tail).

containsRepetition([]) :- fail.
containsRepetition([X | Tail]) :-
	member(X,Tail); containsRepetition(Tail).

%1.A
solution(H1,H2,H3,V1,V2,V3) :-
	word(H1,_,A1,_,_,_,_,_), word(V1,_,B1,_,_,_,_,_), A1=B1,
	word(H1,_,_,_,A2,_,_,_), word(V2,_,B2,_,_,_,_,_), A2=B2,
	word(H1,_,_,_,_,_,A3,_), word(V3,_,B3,_,_,_,_,_), A3=B3,
	word(H2,_,A4,_,_,_,_,_), word(V1,_,_,_,B4,_,_,_), A4=B4,
	word(H2,_,_,_,A5,_,_,_), word(V2,_,_,_,B5,_,_,_), A5=B5,
	word(H2,_,_,_,_,_,A6,_), word(V3,_,_,_,B6,_,_,_), A6=B6,
	word(H3,_,A7,_,_,_,_,_), word(V1,_,_,_,_,_,B7,_), A7=B7,
	word(H3,_,_,_,A8,_,_,_), word(V2,_,_,_,_,_,B8,_), A8=B8,
	word(H3,_,_,_,_,_,A9,_), word(V3,_,_,_,_,_,B9,_), A9=B9.
	
%1.B
solution2(H1,H2,H3,V1,V2,V3) :- 
	solution(H1,H2,H3,V1,V2,V3), not(containsRepetition([H1,H2,H3,V1,V2,V3])).
	
%Question 2
%2.A
isS(0).
isS(s(A)) :-
	isS(A).
	
%2.B
s2int(0,0).
s2int(s(A),Y) :-
	isS(A), s2int(A,B), Y is B+1.

%2.C	
add(0,Y,Z) :- Y=Z.
add(s(X),Y,Z) :-
	add(X,s(Y),Z).

%Question 3
%3.A
range(X,X,[X]) :- !.
range(V1,V2,[X|Tail]) :-
	integer(V1), integer(V2), V1 < V2, X = V1, A is V1+1, range(A, V2, Tail).
	
%3.B
insert_at([X|L],V,1,[Y|L2]) :- 
	[V,X|L] = [Y|L2],!.
insert_at([X|L],V,I,[Y|L2]) :- 
	I > 1, X=Y, I1 is I-1, insert_at(L,V,I1,L2).
	

%Question 4

%4.A
sum([],0).
sum([X|Tail], Total) :-
	sum(Tail,A), Total is A+X.
	
%4.B
add_to_list([],_,[]).
add_to_list([X|Tail1],N,[Y|Tail2]) :-
	A is X+N, Y=A, add_to_list(Tail1,N,Tail2).


locate([], _, []).
locate([X|LineLen], N, [Y|LinePos]) :-
	% First square is empty
	(N1 is N-1, N1>0, locate([X|LineLen], N1, L), add_to_list(L,1,L1), L1=[Y|LinePos]) ;
	% First square is full
	(Y=1, Z is X+1, N1 is N-Z,N1 >= -1, locate(LineLen, N1, L), add_to_list(L,Z,L1), L1=LinePos).
	

%4.C
locateAll([],[],_).
locateAll([X|LenLineAll],[Y|PosLineAll],N) :-
	locate(X,N,Y), locateAll(LenLineAll,PosLineAll,N).
	
%4.D
vecLine2BitLine([],[],0,[]) :- !.
vecLine2BitLine([],[],N,[X|BitLine]) :-
	X=' ',N>0, N1 is N-1, vecLine2BitLine([],[],N1,BitLine), !.
vecLine2BitLine([1|LenLine],[1|PosLine],N,[Z|BitLine]) :-
	Z='*', N>0, N1 is N-1, add_to_list(PosLine, -1, L), vecLine2BitLine(LenLine,L,N1,BitLine), !.
vecLine2BitLine([X|LenLine],[1|PosLine],N,[Z|BitLine]) :-
	Z='*',N>0, N1 is N-1, X1 is X-1, add_to_list(PosLine, -1, L), vecLine2BitLine([X1|LenLine],[1|L],N1,BitLine), !.
vecLine2BitLine(LenLine,PosLine,N,[Z|BitLine]) :-
	Z=' ',N>0, N1 is N-1, add_to_list(PosLine, -1, L), vecLine2BitLine(LenLine,L,N1,BitLine), !.
	
%4.E
vecLineAll2BitLineAll([],[],_,[]).
vecLineAll2BitLineAll([X|LenLineAll],[Y|PosLineAll],N,[Z|BitLineAll]) :-
	vecLine2BitLine(X,Y,N,Z), vecLineAll2BitLineAll(LenLineAll,PosLineAll,N,BitLineAll).
	
%4.F
add_list([],[],[]).
add_list([X|ListToAdd],[],[Z|AddedLists]) :-
	[X] = Z, add_list(ListToAdd,[],AddedLists),!.
add_list([X|ListToAdd],[Y|Lists],[Z|AddedLists]) :-
	[X|Y] = Z, add_list(ListToAdd,Lists,AddedLists).

trans([],[]).
trans([X|Matrix],TransposedMatrix) :-
	trans(Matrix,L), add_list(X,L,TransposedMatrix).
	
	
%4.G
isBitLineLegal([],[]) :- !.
isBitLineLegal(['*'],[1]) :- !.
isBitLineLegal(['*', ' '|BitLine],[1|LenLine]) :-
	isBitLineLegal(BitLine, LenLine),!.
isBitLineLegal(['*', '*'|BitLine],[X|LenLine]) :-
	X1 is X-1, isBitLineLegal(['*'|BitLine], [X1|LenLine]),!.
isBitLineLegal([' '|BitLine],LenLine) :-
	isBitLineLegal(BitLine, LenLine),!.

	
%4.H
isBitLineLegalAll([],[]).
isBitLineLegalAll([X|BitLineAll],[Y|LenLineAll]) :-
	isBitLineLegal(X,Y), isBitLineLegalAll(BitLineAll,LenLineAll).
	
%4.I
solve(RowLenAll,ColLenAll,N,Sol) :-
	locateAll(RowLenAll, RowPosAll, N), vecLineAll2BitLineAll(RowLenAll,RowPosAll,N, BitRowAll),
	locateAll(ColLenAll, ColPosAll, N), vecLineAll2BitLineAll(ColLenAll,ColPosAll,N, BitColAll),
	trans(BitRowAll,BitColAll), Sol=RowPosAll.
	
	


